Now that we understand how a Priority Queue can efficiently find the minimum-weight edge, let's integrate it into a complete, high-performance implementation of Prim's algorithm using an adjacency list. This approach is the standard for finding MSTs in sparse graphs.

  • Start with an arbitrary vertex and add it to a `visited` set.
  • Add all of its adjacent edges to a Priority Queue (PQ).
  • While the MST has fewer than $V-1$ edges, extract the minimum-weight edge from the PQ.
  • If the edge leads to an unvisited vertex, add it to the MST and mark the new vertex as visited.
  • Add all of the new vertex's outgoing edges (to unvisited nodes) to the PQ.
  • The graph is represented with an adjacency list for efficient neighbor lookup.
  • The Priority Queue is implemented as a binary heap for efficient min-extraction.
  • This combination results in an overall time complexity of $O(E \log V)$.
Python: Prim's with Adjacency List & Heap
1import heapq
2
3def prim_mst(graph, start_vertex):
4    # Adjacency list representation of Shared_Graph
5    adj_list = {v: [] for v in graph['vertices']}
6    for u, v, w in graph['edges']:
7        adj_list[u].append((v, w))
8        adj_list[v].append((u, w))
9
10    mst = []
11    visited = {start_vertex}
12    # PQ stores (weight, from_vertex, to_vertex)
13    pq = [(w, start_vertex, v) for v, w in adj_list[start_vertex]]
14    heapq.heapify(pq)
15    
16    total_cost = 0
17
18    while pq and len(mst) < len(graph['vertices']) - 1:
19        weight, u, v = heapq.heappop(pq)
20        
21        if v not in visited:
22            visited.add(v)
23            mst.append((u, v, weight))
24            total_cost += weight
25            for neighbor, neighbor_weight in adj_list[v]:
26                if neighbor not in visited:
27                    heapq.heappush(pq, (neighbor_weight, v, neighbor))
28    
29    return mst, total_cost